package datastructure.book.tujiesuanfa.string._2_more;

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class Solution1 {

    /**
     * 输入: message = "  hello   world!  "
     * 输出: "world! hello"
     *
     * 输入: message = "   "
     * 输出: ""
     *
     * 输入: message = ""
     * 输出: ""
     */
    public String reverseMessage(String message) {
        if (message == null || message.isEmpty()) {
            return message;
        }
        int i = message.length()-1;int j = message.length()-1;
        StringBuilder sb = new StringBuilder();
        while (i >= 0) {
            while (i >= 0 && message.charAt(i) == ' ') {
                i--;j--;
            }
            while (i >= 0 && message.charAt(i) != ' ') {
                i--;
            }
            if (i >= 0) {
                sb.append(message,i+1,j+1).append(" ");
                j = i;
            } else if (i != j) {
                sb.append(message,i+1,j+1);
            }
        }
        if (sb.length() != 0 && sb.charAt(sb.length() - 1) == ' ') {
            sb.deleteCharAt(sb.length()-1);
        }
        return sb.toString();
    }

    /**
     * 将 password 前 target 个字符按原顺序移动至字符串末尾
     * 使用O(1)空间复杂度，只使用原数组不新建数组
     * 1 <= target < password.length <= 10000
     * 输入: password = "s3cur1tyC0d3", target = 4
     * 输出: "r1tyC0d3s3cu"
     */
    public String dynamicPassword(char[] passwordArr, int target) {
        for (int i = 0; i < target / 2; i++) {
            char temp = passwordArr[i];
            passwordArr[i] = passwordArr[target-i-1];
            passwordArr[target-i-1] = temp;
        }
        int i = target; int j = passwordArr.length-1;
        while (i < j) {
            char temp = passwordArr[i];
            passwordArr[i] = passwordArr[j];
            passwordArr[j] = temp;
            i++;j--;
        }
        i = 0;j = passwordArr.length-1;
        while (i < j) {
            char temp = passwordArr[i];
            passwordArr[i] = passwordArr[j];
            passwordArr[j] = temp;
            i++;j--;
        }
        return new String(passwordArr);
    }

    @Test
    public void test1(){
        System.out.println(myAtoi("4235"));
    }

    /**
     * 不使用库函数的字符串转整数，结果为32位有符号整数
     * 前导只能是空格
     * 小于 −2^31 的整数应该被固定为 −2^31 ，大于 2^31 − 1 的整数应该被固定为 2^31 − 1 。
     * 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
     * 例如："123" -> 123， "0032" -> 32，"  -0123450  22 nk " -> -123450
     * "bb -9" -> 0,"  --9" -> 0
     */
    public int myAtoi(String str) {
        if (str == null || str.isEmpty()) {
            return 0;
        }
        int i=0,j=0;
        boolean isSmallZero = false;
        int[][] states = {
              //' ', +, d, o
                { 0, 1, 2, -1},//' '
                { -1, -1, 2,-1},//+
                { 3, 3, 2, 3},//d
        };
        char[] charArray = str.toCharArray();
        int state = 0;
        long result = 0;long index = 10;
        for (char c : charArray) {
            if (c == ' ') {
                state = states[state][0];
            } else if (c == '+') {
                state = states[state][1];
            } else if (c == '-') {
                state = states[state][1];
                if (state == 1) {
                    isSmallZero = true;
                }
            } else if (c >= '0' && c <= '9') {
                state = states[state][2];
            } else {
                state = states[state][3];
            }
            if (state == -1) {
                return 0;
            }
            if (state == 2) {
                result = result * index;
                result += (c - 48);
                if (isSmallZero) {
                    if ((-result) <= (Integer.MIN_VALUE)) {
                        return Integer.MIN_VALUE;
                    }
                } else {
                    if (result >= Integer.MAX_VALUE) {
                        return Integer.MAX_VALUE;
                    }
                }
            } else if (state == 3) {
                break;
            }
        }
        return isSmallZero ? (int)-result:(int)result;
    }

    /**
     * 有效数字（按顺序）可以分成以下几个部分：
     * 1、若干空格
     * 2、一个 小数 或者 整数
     * 3、（可选）一个 'e' 或 'E' ，后面跟着一个 整数
     * 4、若干空格
     * 小数（按顺序）可以分成以下几个部分：
     *      （可选）一个符号字符（'+' 或 '-'）
     *      下述格式之一：
     *          至少一位数字，后面跟着一个点 '.'
     *          至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
     *          一个点 '.' ，后面跟着至少一位数字
     * 整数（按顺序）可以分成以下几个部分：
     *      （可选）一个符号字符（'+' 或 '-'）
     *       至少一位数字
     * 举例：
     * 有效数字：["2", "0089", "-0.1", "  +3.14"  , "4.", "  -.9  ", "2e10", "  -90E3  ",
     *          "3e+7", "+6e-1", "53.5e93", "-123.456e789"]
     * 无效数字：["abc", "1e", "e3", "99e2.5", "--6", "-+3", "95  54e53", ".0e" ,"0.e"]
     */
    public boolean validNumber(String s) {
        if (s == null || s.isEmpty()) {
            return false;
        }
        //开始状态(" ,"+,"1,".)
        HashMap<Character, Integer> state0 = new HashMap<>();
        state0.put(' ',0);state0.put('+',1);state0.put('d',2);state0.put('.',4);
        //e前符号("+1,"+.)
        HashMap<Character, Integer> state1 = new HashMap<>();
        state1.put('d',2);state1.put('.',4);
        //小数点前面数字("1.1","1.","1.e","1 ")，可以结束
        HashMap<Character, Integer> state2 = new HashMap<>();
        state2.put('d',2);state2.put('.',3);state2.put('e',5);state2.put(' ',8);
        //数字后点、点后数字，可以结束
        HashMap<Character, Integer> state3 = new HashMap<>();
        state3.put('d',3);state3.put('e',5);state3.put(' ',8);
        //空格，符号后点
        HashMap<Character, Integer> state4 = new HashMap<>();
        state4.put('d',3);
        //e
        HashMap<Character, Integer> state5 = new HashMap<>();
        state5.put('+',6);state5.put('d',7);
        //e后符号
        HashMap<Character, Integer> state6 = new HashMap<>();
        state6.put('d',7);
        //e后数字，可以结束
        HashMap<Character, Integer> state7 = new HashMap<>();
        state7.put('d',7);state7.put(' ',8);
        //末尾空格，可以结束
        HashMap<Character, Integer> state8 = new HashMap<>();
        state8.put(' ',8);
        HashMap<Character,Integer>[] states = new HashMap[]{
                state0,state1,state2,state3,state4,state5,state6,state7,state8
        };
        int state = 0;
        for (char c : s.toCharArray()) {
            char achar = '?';
            if (c >= '0' && c <= '9') {
                achar = 'd';
            } else if (c == 'e' || c == 'E') {
                achar = 'e';
            } else if (c == '+' || c == '-') {
                achar = '+';
            } else if (c == ' ' || c == '.') {
                achar = c;
            }
            if (states[state].containsKey(achar)) {
                state = states[state].get(achar);
            } else {
                return false;
            }
        }
        return state == 2 || state == 3 ||state == 7 ||state == 8;
    }
}
